package sf.sort;

public class HeapSort implements Sort {
    @Override
    public void sort(int[] unsorted) {
        // 建立大堆根
        buildHeap(unsorted, unsorted.length);
        for (int i = unsorted.length; i > 1; i--) {
            int temp = unsorted[0];
            unsorted[0] = unsorted[i-1];
            unsorted[i-1] = temp;
            adjustHeap(unsorted,0, i-1);
        }
    }

    public void buildHeap(int[] nums, int n) {
        // 建立大堆根 n / 2
        for (int i = n /  2 - 1; i >= 0; i--) {
            adjustHeap(nums, i , n);
        }
    }

    private void adjustHeap(int[] nums, int i, int n) {
        int temp = nums[i];
        for (int j = i * 2 + 1; j < n; j = 2 * j + 1) {
            if (j + 1 < n && nums[j+1] > nums[j]) {
                j ++;
            }
            // 如果
            if (temp < nums[j]) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                i = j;// 因为根调整了后会导致后面的根也变化了
            }
        }
    }
}
